//
// Description: 199. 二叉树的右视图
// Created by Loading on 2022/5/3.
//

#include <bits/stdc++.h>
#include <Data_Structure_Definition.h>
#include <Utils.h>

using namespace std;

vector<int> rightSideView(TreeNode *root) {
    if (!root) {
        return {};
    }
    vector<int> res;
    queue<TreeNode *> q;
    q.emplace(root);
    // 层序遍历
    while (!q.empty()) {
        int size = q.size();
        for (int i = 0; i < size; ++i) {
            auto node = q.front();
            q.pop();
            if (node->left) {
                q.emplace(node->left);
            }
            if (node->right) {
                q.emplace(node->right);
            }
            // 每一层取最后一个
            if (i == size - 1) {
                res.emplace_back(node->val);
            }
        }
    }

    return res;
}

int main() {
    vector<int> nums{1, 2, 3, -1, 5, -1, 4};
    auto root = generateTreeNode(nums);
    auto res = rightSideView(root);
    for (auto x : res) {
        cout << x << ' ';
    }

    return 0;
}